Recurrence

This chapter introduces recursive algorithms and how they can be analyzed.

We'll cover the following

The word recurrence literally means the fact of occurring again.

widget

Merge Sort#

Merge sort is a typical textbook example of a recursive algorithm. The idea is very simple: We divide the array into two equal parts, sort them recursively, and then combine the two sorted arrays. The base case for recursion occurs when the size of the array reaches a single element. An array consisting of a single element is already sorted.

We'll determine the time complexity of merge sort by unrolling the recursive calls made by the algorithm to itself, and examining the cost at each level of recursion. The total cost is the sum of individual costs at each level.

The running time for a recursive solution is expressed as a recurrence equation (an equation or inequality that describes a function in terms of its own value on smaller inputs). The running time for a recursive algorithm is the solution to the recurrence equation. The recurrence equation for recursive algorithms usually takes on the following form:

Running Time = Cost to divide into n subproblems + n * Cost to solve each of the n problems + Cost to merge all n problems

In the case of merge sort, we divide the given array into two arrays of equal size, i.e. we divide the original problem into sub-problems to be solved recursively.

Following is the recurrence equation for merge sort. Running Time = Cost to divide into 2 unsorted arrays + 2 * Cost to sort half the original array + Cost to merge 2 sorted arrays

T(n)=Cost to divide into 2 unsorted arrays+2∗T(n2)+Cost to merge 2 sorted arrays when n>1T(n) = Cost\:to\:divide\:into\:2\:unsorted\:arrays + 2* T(\frac{n}{2}) + Cost\:to\:merge\:2\:sorted\: arrays \:when \:n > 1

T(n)=O(1)  when n=1T(n) = O(1) \:\:when\: n = 1

Remember the solution to the recurrence equation will be the running time of the algorithm on an input of size n.

Merge Sort Recursion Tree#

Working of Merge Sort
Working of Merge Sort

Merge Sort Implementation#

Cost to divide#

Line-19 is the cost of dividing the original problem into two sub-problems, with each one of them half the size of the original array. The mathematical operation takes place in constant time, and we can say that the cost to divide the problem into 2 subproblems is constant. Let’s say it is denoted by d.

Cost to Merge#

Line-27 to 55 is the cost to merge two already-sorted arrays. Note the use of a scratch array here. Merge Sort can be implemented in-place but doing so isn’t trivial. For now, we’ll stick to using an additional array. You’ll notice that the merge part has two loops:

  1. for loop line 32 to 34

  2. while loop line 37 to 55

Note: Both the loops iterate for end-start+1, which is the size of the sub-problem the algorithm is currently working on. The cost of merging two arrays varies with the input size, as follows:

  • Size of each array = n2\frac{n}{2}, Cost to merge = 2 * n2\frac{n}{2}= nn

  • Size of each array = n4\frac{n}{4}, Cost to merge = 2 * n4\frac{n}{4} = n2\frac{n}{2}

  • Size of each array = n8\frac{n}{8}, Cost to merge = 2 * n8\frac{n}{8} = n4\frac{n}{4}

  • Size = 1, Cost = 1 - base case for recursion

Cost to solve 2 subproblems of half the size#

The cost to solve each of the two sub-problems (of half the size of the original array) isn’t so straightforward, as each of them is expressed as a recursive call to merge sort.

Let’s start with the base case: when the problem size becomes a single element, the 1-element array is already sorted, and the recursion bottoms out. The cost of solving the base case is constant time. For simplicity, let’s assume it’s one.

Solution Set 2

Recurrence Part II